Depending on the application, mesh decompositions may have different requirements regarding the properties of the constituent elements. For example, for skeleton extraction, prior art methods produce decompositions With complex components, possibly with higher than zero-genus. [See S. Katz and A. Tal, ACM TOG. Special issue for SIGGRAPH conference, Proceedings of Siggraph 2003, 2003]. Such decompositions may be suitable for restricted problems such as approximate skeleton extraction, but would require further, non-trivial processing for most other applications. For example, texture mapping involves associating 2D color images with regions of a 3D mesh. To establish such an association, an atlas consisting of charts that can be easily mapped to the planar domains of the images is necessary. The same holds true for semi-regular remeshing problems, where the charts serve as faces of a coarse polyhedral base domain over which the remeshing is performed.
Attention is drawn to the problem of finding atlas decompositions which satisfy several important properties:                1. The number of patches in the atlas is small. Typically, the complexity of algorithms processing the patches is proportional to the number of patches. Obviously, for efficiency reasons, it is highly desirable to keep this number as small as possible.        2. Patches should be compact, with nice and simple shapes. For instance, it is common practice for textures to be packed into a single, nearly square image for rendering purposes. Shapes with irregular boundaries make packing inefficient and waste texture memory. Also, it becomes easier to apply editing operations to textures directly when they appear as humanly recognizable pieces. Similarly, for the purpose of remeshing it the faces of the base domain faces should be nicely-shaped polygons. Last but not least, for parameterization purposes, a simple shape often translates into a simpler parameterization algorithm and reduced distortion.        
Prior methods for mesh decomposition can be classified into two main categories, according to whether they require some degree of user involvement in defining the component charts or not. Semi-automatic methods require manual outlining of one or more chart boundaries or some other defining properties of the charts. (See for example V. Krishnamurthy and M. Levoy, Fitting Smooth Surfaces to Dense Polygon Meshes, Proceedings of SIGGRAPH 96, pp. 313-324, 1996.) Fully automatic methods produce atlases without the need for interactive adjustment of charts. Our proposed method falls into the latter category and solves a significant number of problems which prior art fails to address.